package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
 **/
public class No014 {

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：35.4 MB, 在所有 Java 提交中击败了8.56%的用户
     */
    public int cuttingRope(int n) {
        int[] dp = new int[n - 1];
        dp[0] = -1;

        for (int i = 1; i < n; i++) {
            int bak = n;
            int multi = 1;
            int flag = i + 1;
            while (flag >= 1) {
                int tmp = bak / flag;
                multi = multi * tmp;
                bak -= tmp;
                flag--;
            }
            dp[i] = multi;

            if (multi <= dp[i - 1]) {
                return dp[i - 1];
            }
        }

        return dp[n - 1];
    }
}
